import java.util.ArrayList;
import java.util.List;

/**
 * 1791. 找出星型图的中心节点
 * https://leetcode-cn.com/problems/find-center-of-star-graph/
 */
public class Solutions_1791 {
    public static void main(String[] args) {
        int[][] edges1 = {{1, 2}, {2, 3}, {4, 2}};  // output: 2
        int[][] edges2 = {{1, 2}, {5, 1}, {1, 3}, {1, 4}};  // output: 1

        List<int[][]> inputs = new ArrayList<>();
        inputs.add(edges1);
        inputs.add(edges2);

        for (int[][] input : inputs) {
            int result = findCenter(input);
            System.out.println(result);
        }
    }

    /**
     * 解法二：利用题目说明
     * 说明：一定有 1 个中心节点，且图中只有 n - 1 条边
     * 即说明了只有中心节点与所有节点相连，非中心节点只与中心节点相连
     * 即非中心节点只有一条边，中心节点出现在每一个 edges[i] 数组中
     */
    public static int findCenter(int[][] edges) {
        int[] arr1 = edges[0];
        int[] arr2 = edges[1];

        if (arr1[0] == arr2[0] || arr1[0] == arr2[1]) {
            return arr1[0];
        } else {
            return arr1[1];
        }
    }

    /**
     * 解法一：哈希计数
     * 若有 4 个节点，则中心节点有 3 条边，分别与其他 3 个节点相连
     * 即哪个屮有 3 条边，即是中心节点
     */
    public static int findCenter2(int[][] edges) {
        int[] counts = new int[100001];
        for (int[] edge : edges) {
            counts[edge[0]] ++;
            counts[edge[1]] ++;
        }
        for (int i = 1; i < counts.length; i++) {
            if (counts[i] == edges.length) {
                return i;
            }
        }
        return -1;
    }
}
